In a computer network for transmitting information, messages can be restricted from being transmitted from selected source devices to selected destination devices. In known computer networks, this form of restriction is known as xe2x80x9caccess controlxe2x80x9d and is performed by routers, which route messages (in the form of individual packets of information) from source devices to destination devices. One known technique for access control is for each router to perform access control by reference to one or more ACLs (access control lists); the ACL describes which selected source devices are permitted (and which denied) to send packets to which selected destination devices.
In a known standard for ACL format, each ACL includes a plurality of access control specifiers, each of which selects a range of sender and destination IP address prefix or subnet, and port, and provides that packet transmission from that selected set of senders to that selected set of destinations is either specifically permitted or specifically denied. ACLs are associated with input interfaces and independently with output interfaces for each router. In known routers such as those manufactured by Cisco Systems, Inc., of San Jose, Calif., the router is provided with an ACL using an ACL command language, interpreted by operating system software for the router, such as the IOS operating system.
One problem in the known art is that processing of packets to enforce access control according to the ACL is processor-intensive and can therefore be relatively slow, particularly in comparison with desired rates of speed for routing packets. This problem is exacerbated when access control is enforced for packets using software in the router, because software processing of the ACL can be quite slow relative to hardware processing of the packet for routing.
One known solution is to reduce the number of packets for which access control requires actual access to the ACL. In a technique known as xe2x80x9cnetflow switching,xe2x80x9d packets are identified as belonging to selected xe2x80x9cflows,xe2x80x9d and each packet in a flow is expected to have identical routing and access control characteristics. Therefore, access control only requires reference to the ACL for the first packet in a flow; subsequent packets in the same flow can have access control enforced identically to the first packet, by reference to a routing result cached by the router and used for the entire flow.
Netflow switching is further described in detail in the following patent applications:
U.S. application Ser. No. 08/581,134, titled xe2x80x9cMethod For Traffic Management, Traffic Prioritization, Access Control, and Packet Forwarding in a Datagram Computer Networkxe2x80x9d, filed Dec. 29, 1995, in the name of inventors David R.
Cheriton and Andreas V. Bechtolsheim, assigned to Cisco Technology, Inc., attorney docket number CIS-019;
U.S. application Ser. No. 08/655,429, titled xe2x80x9cNetwork Flow Switching and Flow Data Exportxe2x80x9d, filed May 28, 1996, in the name of inventors Darren Kerr and Barry Bruins, and assigned to Cisco Technology, Inc., attorney docket number CIS-016; and
U.S. application Ser. No. 08/771,438, titled xe2x80x9cNetwork Flow Switching and Flow Data Exportxe2x80x9d, filed Dec. 20, 1996, in the name of inventors Darren Kerr and Barry Bruins, assigned to Cisco Technology, Inc., attorney docket number CIS-017.
These patent applications are collectively referred to herein as the xe2x80x9cNetflow Switching Disclosuresxe2x80x9d. Each of these applications is hereby incorporated by reference as if fully set forth herein.
While netflow switching achieves the goal of improving the speed of enforcing access control by the router, it still has the drawback that comparing at least some incoming packets against the ACL must be performed using software. Thus, the relative slowness required by software processing of the ACL is not completely avoided.
A second problem in the known art is that software processing of the ACL takes increased time when the ACL has numerous entries, such as when the requirements for access control are complex. The more entries in the ACL, the more time is expected to be required for software processing of the ACL, and thus the more time is expected to be required for software enforcement of access control. Since known routers require at least some software enforcement of access control, this reduces the routing speed at which the router can operate.
For example, for some large ACLs, routing speed can be reduced to as low as about 10,000 packets per second. However, the wirespeed rate of incoming packets is presently (for relatively short packets) about 1.5 million packets per gigabit per second transmission capacity, or in the range of about tens to hundreds of millions of packets per second for gigabit networks. Since it would be desirable for routers to operate at speeds comparable to the wirespeed, the present limitation on router speed is unacceptably low.
Accordingly, it would be desirable to provide a method and system for hardware processing of ACLs and thus hardware enforcement of access control. This advantage is achieved in an embodiment of the invention in which a sequence of access control specifiers from an ACL are recorded in a CAM (content-addressable memory), and in which matching (or lack of matching) of information from the packet header to specifiers recorded in the CAM are used to enforce access control.
The invention provides a method and system for hardware processing of ACLs and thus hardware enforcement of access control. A sequence of access control specifiers from an ACL are recorded in a CAM, and information from the packet header is used to attempt to match selected source and destination IP addresses or subnets, ports, and protocols, against all the ACL specifiers at once. Successful matches are input to a priority selector, which selects the match with the highest priority (that is, the match that is first in the sequence of access control specifiers). The specified result of the selected match is used to permit or deny access for the packet without need for software processing, preferably at a rate comparable to wirespeed.
In a preferred embodiment, the CAM includes an ordered sequence of entries, each of which has an array of ternary elements for matching on logical xe2x80x9c0xe2x80x9d, logical xe2x80x9c1xe2x80x9d, or on any value, and each of which generates a match signal. The ACL entered for recording in the CAM can be optimized to reduce the number of separate entries in the CAM, such as by combining entries which are each special cases of a more general access control specifier.
A router including the CAM can also include preprocessing circuits for certain range comparisons which have been found both to be particularly common and to be otherwise inefficiently represented by the ternary nature of the CAM. For example, comparisons of the port number against known special cases, such as xe2x80x9cgreater than 1023xe2x80x9d and xe2x80x9cwithin the range 6000 to 6500xe2x80x9d, can be treated by circuitry for performing range comparisons or by reference to one or more auxiliary CAMs.
The invention can also be used to augment or override routing decisions otherwise made by the router, so as to implement QOS (quality of service), and other administrative policies, using the CAM.